For enabling the detection or even correction of errors which occured during transmission or storage of data, it is usual to introduce redundancy by appending some check bits to the mere data bits. These extra bits can be either simple parity bits, e.g. one for each of a number of data sub-fields, or they can be a group of interrelated ECC (Error Checking and Correction) bits which are generated by an elaborated procedure. Such procedures include use of an H-matrix or division by a generator polynomial.
In many error correcting schemes, a syndrome is generated on the receiving side which indicates whether or what errors occured. The syndrome can be obtained e.g. by generating from the data portion of the stored or transmitted block an ECC field in the same way as the original ECC field was generated, and then combining the two (received and locally generated) ECC fields e.g. by an XOR operation. If both ECC fields were equal, the syndrome will be all zeros indicating that no error occured. Otherwise, a particular syndrome pattern will be obtained for each different error situation. However, in most ECC schemes the syndrome--though it uniquely identifies at least the correctable errors--does not directly show the position of the erroneous bits but must be first converted to obtain an error pointer, i.e. a direct or simply coded error position address.
The design and utilization of error checking and correcting codes, and the generation and use of syndromes in an error correction process are generally described and reviewed in a book by W. W. Peterson et al. entitled "Error Correcting Codes", MIT Press, Cambridge/Mass., 1972.
Numerous specific techniques and codes for error correction using syndromes are known in the art. U.S. Pat. No. 3,685,014 to M. Y. Hsiao et al. is concerned with an "Automatic double error detection and correction device" which generates syndrome bits from check bits and data bits of a binary word. The disclosed process requires several sequential operations to enable a first bit error correction, and further requires the generation of a second syndrome and additional sequential operations to enable correction of a second erroneous bit.
A similar error correction scheme is disclosed in U.S. Pat. No. 4,236,247 to C. E. Sundberg "Apparatus for correcting multiple errors in data words read from a memory". This scheme also requires sequential operations and the generation of a second syndrome if two errors are to be corrected.
In U.S. Pat. No. 4,030,067 to T. H. Howell et al., entitled "Table lookup direct decoder for double-error correcting (DEC) BCH codes using a pair of syndromes" another ECC technique is described. Two syndromes are generated and are then subjected to sequential multiplying and translating (table look-up) operations for generating two error-indicating words which are used for correcting the erroneous bits. The sequential processing operations by which actually equations are solved need a given amount of time which may be too long for certain applications.
U.S. Pat. No. 4,107,652 to J. Tanahashi et al. "Error correcting and controlling system" also discloses error correction apparatus including syndrome generating means. The error bit positions corresponding to respective syndromes are kept in a storage, and syndromes are used as addressing inputs to this storage. This requires a large amount of storage space because for each possible syndrome a respective error pattern (or non-correctable error indicating pattern) is to be stored. If a reduction in storage will be made, flexibility in the format of error pointers (error indicating patterns) is lost, and circuitry used for generating syndromes can no more be simultaneously used for locally generating ECC fields from the data bits. Furthermore, extra circuitry is required for determining the type of error that occured and was corrected.
If of a large set of possible addresses only a randomly distributed subset has corresponding entries in a storage, e.g. when a high-speed buffer or cache holds selected entries of main storage, a technique generally known as "hashing" can be used for converting the given addresses into more suitable ones for the specific storage. A brief general description of hashing is given in the "Encyclopaedia of Computer Science", Editor A. Ralston, Van Nostrand N.Y. 1976 on pages 604-606. U.S. Pat. No. 4,215,402 to G. R. Mitchell, "Hash index table hash generator apparatus", is an example for the use of hashing in virtual storage addressing.
One disadvantage of known hashing techniques is the fact that the same hash word can be generated on the basis of several different input addresses. This can lead to collisions so that at the location addressed by each hash word, a replication of the full address must be stored to determine which one of the several possible full addresses lead to this entry. Furthermore, an escape mechanism must be provided to enable the generation of additional hash words when the basic hash word is "occupied" already, and a corresponding chain search must be made when such entries are to be retrieved.
It is an object of present invention to devise a method and apparatus for error detection and correction based on the generation of syndrome words from received information blocks comprising data bits and ECC bits.
It is another object to devise an error correction technique using less storage space than would usually be required to store error control information for all generated syndromes, but still using a minimum in additional hardware and processing time for converting syndromes into information pointing to correctable errors.
A further object of the invention is an error-correcting mechanism which allows free and flexible selection of formats for the error pointers developed from syndromes.
Another object is to enable the generation of error-type indications simultaneously with the generation of information pointing to or addressing the error bits which are to be corrected.
Still another object is to devise an error correction technique which allows, based on any known DEC-TED code with byte error correction capability, the correction of two randomly located errors and the correction of three or four errors which are located in any compact sub-group of bits.
One other object is to provide a hashing technique for converting input words or names to assigned output words or values, that avoids collision and chain-searching situations but still enables a good storage utilization.